/*
 * Author: Wang Hsutung
 * Date: 2015/12/04
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stack>
#include <utility>
#include <algorithm>

using std::pair;

/* `n' 为整形数组 `a' 的大小 */
void quickSort(int a[], int n)
{
    std::stack<pair<int, int>> stk;
    if (n <= 1)
        return;
    stk.push(pair<int, int>(0, n)); // 记录区间的栈

    while (!stk.empty()) {
        pair<int, int> range = stk.top();
        stk.pop();
        int keyindex = range.first; // keyindex 为枢纽值下标

        /* 对元素范围 [first, second) 进行一趟快排 */
        for (int i = range.first; i < range.second; ++i) {
            if (a[i] < a[range.first])
                std::swap(a[++keyindex], a[i]);
        }
        std::swap(a[range.first], a[keyindex]);

        /* 若子区间的长度超过 1，则需要进一步排序 */
        if (range.second - (keyindex + 1) > 1)
            stk.push(pair<int, int>(keyindex + 1, range.second));
        if (keyindex - range.first > 1)
            stk.push(pair<int, int>(range.first, keyindex));
    }
}

int main(int argc, char *argv[])
{
    int arrsize, randmax, *arr;

    std::cout << " Please input the size of your array and the max value: ";
    std::cin >> arrsize >> randmax;
    arr = new int[arrsize];

    /* 用随机数初始化数组 */
    std::srand(std::time(NULL));
    for (int i = 0; i < arrsize; ++i)
        arr[i] = std::rand() % (randmax + 1);

    std::cout << "\n(*) Those are " << arrsize
        << " randomly generated integers in array `A\':\n";
    for (int i = 0; i < arrsize ; ++i)
        std::cout << " " << arr[i];

    /* 快速排序 */
    quickSort(arr, arrsize);

    std::cout << "\n\n(#) Aftet QuickSort the array `A\' became:\n";
    for (int i = 0; i < arrsize; ++i)
        std::cout << " " << arr[i];

    delete[] arr;
    std::cout << std::endl;
    std::exit(EXIT_SUCCESS);
}

